package leetcode_2401_2500;

import node.ListNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeeCode_2487 {
    public static void main(String[] args) {
        System.out.println(removeNodes(new ListNode(5, new ListNode(2, new ListNode(13, new ListNode(3, new ListNode(8)))))));
    }
    private static ListNode removeNodes(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = head;
        List<Integer> list = new ArrayList<>();
        list.add(0);
        while (cur != null){
            list.add(cur.val);
            cur = cur.next;
        }
        int[] maxes = new int[list.size()];
        int max = 0;
        for(int i = list.size() - 1; i >= 0; i--){
            max = Math.max(max, list.get(i));
            maxes[i] = max;
        }
        ListNode pre = dummy, now = head;
        int index = 1;
        while (index < list.size() - 1){
            if (now.val < maxes[index]){
                pre.next = now.next;
                now = pre.next;
                index++;
            }else {
                pre = pre.next;
                now = now.next;
                index++;
            }
        }
        return dummy.next;
    }
}
